Blog • 一个最简单的编译器的实现 |
您所在的位置：网站首页 › 编译原理 龙虎鲸 › Blog • 一个最简单的编译器的实现 |
Blog • 一个最简单的编译器的实现
|
本文将会带领读者做出一个简单的类C（但比C简单无数倍）语言的编译器。 参考代码在这里，本文完成时的版本是这个。 这个语言支持： 两种基本数据类型：int 和 double 上述数据类型的数组 两种控制结构：if（当然可以有可选的 else）和 while 基本数学和关系运算：+、-、*、/、=、==、!=本文假设读者是一个比较熟练的C语言1程序猿，并具有基本的正则表达式知识。 同时本文读者应当熟悉 flex & bison 的基本使用，如果你对此不熟悉，可以参考我的 另一篇文章。 编译过程首先本文中所述的编译器编译一个程序的过程如下2：
显然很多代码都不用我们自己写，生在这样一个有丰富工具的时代既是幸运，也是一种不幸。 词法分析在此给出 flex 的关键部分代码： "char" {yylval.type=Char; return TYPE;} "int" {yylval.type=Int; return TYPE;} "double" {yylval.type=Double; return TYPE;} "string" {yylval.type=String; return TYPE;} "if" {return IF;} "else" {return ELSE;} "while" {return WHILE;} "print" {return PRINT;} ([-])?[0-9]+ {yylval.int_value=atoi(yytext); return INT_LITERAL;} ([-])?[0-9]+\.[0-9]* {yylval.double_value=atof(yytext); return DOUBLE_LITERAL;} [a-zA-Z][0-9a-zA-Z_]* {yylval.string_value=strdup(yytext); return IDENTIFY;} "==" {return EQUAL;} "!=" {return NONEQUAL;} "" {return *yytext;} ">=" {return GREATEREQ;} "+" {return *yytext;} "-" {return *yytext;} "*" {return *yytext;} "/" {return *yytext;} "[" {return *yytext;} "]" {return *yytext;} [ \t] {} . {return *yytext;} 语法分析在此给出 bison 的关键部分代码： program: program statement | ; assign: '=' expression ; defineStatement: TYPE IDENTIFY ';' | TYPE IDENTIFY '[' INT_LITERAL ']' ';' | TYPE IDENTIFY assign ';' ; assignStatement: referenceExpression assign ';' ; statementList: statementList statement | ; block: '{' statementList '}' ; ifStatement: IF expression block | IF expression block ELSE block ; whileStatement: WHILE expression block ; printStatement: PRINT '(' expression ')' ';' ; statement: defineStatement | assignStatement | block | ifStatement | whileStatement | printStatement ; referenceExpression: IDENTIFY | IDENTIFY '[' expression ']' atomExpression: INT_LITERAL | DOUBLE_LITERAL | referenceExpression | '(' expression ')' ; unaryOperator: '+' | '-' | '!' ; unaryExpression: atomExpression | unaryOperator atomExpression ; binaryOrAtomExpression: unaryExpression | binaryOrAtomExpression '+' unaryExpression | binaryOrAtomExpression '-' unaryExpression | binaryOrAtomExpression '*' unaryExpression | binaryOrAtomExpression '/' unaryExpression | binaryOrAtomExpression '' unaryExpression | binaryOrAtomExpression LESSEQ unaryExpression | binaryOrAtomExpression GREATEREQ unaryExpression | binaryOrAtomExpression EQUAL unaryExpression | binaryOrAtomExpression NONEQUAL unaryExpression ; expression: binaryOrAtomExpression ;注意此处没有给出相应的行为代码，因为首先需要理解AST才能明白这些行为。 AST（抽象语法树）抽象语法树将语法分析得到的语法单元组织成树状。 基本上每个statement和expression都可以对应AST上的一个node。 本编译器的AST设计部分参考了llvm的AST设计。
因此我们就能写出 %union 和 %type： %union { int int_value; double double_value; char* string_value; ASTNode* node; SymbolType type; }; %token TYPE %token IDENTIFY %token INT_LITERAL %token DOUBLE_LITERAL %token STRING INT DOUBLE %token IF ELSE WHILE FOR %token LESSEQ GREATEREQ EQUAL NONEQUAL %token PRINT %left '>' '' unaryExpression {$$=(ASTNode*)create_binary_operation_result('>',(RValue*)$1,(RValue*)$3);} | binaryOrAtomExpression LESSEQ unaryExpression {$$=(ASTNode*)create_binary_operation_result(LESSEQ, (RValue*)$1,(RValue*)$3);} | binaryOrAtomExpression GREATEREQ unaryExpression {$$=(ASTNode*)create_binary_operation_result(GREATEREQ,(RValue*)$1,(RValue*)$3);} | binaryOrAtomExpression EQUAL unaryExpression {$$=(ASTNode*)create_binary_operation_result(EQUAL, (RValue*)$1,(RValue*)$3);} | binaryOrAtomExpression NONEQUAL unaryExpression {$$=(ASTNode*)create_binary_operation_result(NONEQUAL, (RValue*)$1,(RValue*)$3);} 符号表与作用域这个编译器由于不涉及多文件，也没有复杂类型，符号表的设计较为简单，维护一个全局符号表栈即可： typedef enum { Bool, Int, String, Double, Array } SymbolType; typedef struct { SymbolType type; bool mutable; char *name; size_t namespace_id; } Symbol; typedef struct { Symbol base; SymbolType elementType; size_t length; } ArraySymbol; typedef struct { size_t length; Symbol **symbols; size_t namespace_id; } SymbolTableFrame; typedef struct { size_t length; SymbolTableFrame **frames; } SymbolTableStack; SymbolTableStack symbol_table_stack = {0, NULL}; void push_frame(); void pop_frame(); void add_symbol(Symbol *symbol); Symbol *get_symbol(char *name);其中 get_symbol 从栈顶向栈底寻找名字为 name 的符号。 在 add_symbol 时，会设置 symbol 的 namespace_id 为 frame 的 namespace_id，这在代码生成时会作为变量名称的一部分出现。 在语法分析时： block: '{' {push_frame();} statementList '}' {$$=$3;pop_frame();} ;每遇到一个 block，就 push 一个 frame，离开 block 时 pop 即可，这样这个 block 内声明的 symbol 就会获得一个和这个 block 对应的 namespace_id。 在使用 symbol 时，由于刚刚进入的 block 对应的 frame 在栈顶附近，故会优先在这个 frame 中寻找名字为 name的符号，在这个 frame 中找不到时才会逐级向上寻找，这样就实现了作用域。 目标代码生成为了方便代码跨平台和借用 llvm 的优秀的代码优化能力3，我们的目标代码是 LLVM IR。 LLVM IR兼有高级语言和汇编的特点，比如： LLVM IR 是强类型的 LLVM IR 中的许多控制结构类似汇编，如 if、while 等控制结构都通过 br 跳转来表示 LLVM IR 中的”局部变量”相当程度上是一个”寄存器”，但 LLVM IR 逻辑上有无限多的这种”寄存器”，需要注意的是 LLVM IR是一种 SSA 形式的 IR，所以一个”寄存器”只能赋值一次。 LLVM 的很多操作都类似汇编的格式，如：%a = add i32 1, %b 类似 add %a, 1, %b在此讲一些我们用到的 LLVM IR： 变量定义用 alloca 在栈上开辟一块空间： %i_0 = alloca i32注意 alloca 返回的是一个指针。 变量的赋值使用 store： store i32 0, i32* %i_0即将 0 放入 %i_0 所指的变量中。 读取变量的值用 load： %temp = load i32, i32* %i_0即将 %i_0 所指的变量中的值放入 %temp 寄存器中。 运算以加法为例： %temp_22 = add i32 %temp_21, 1即将 %temp_21 + 1 的值放入 %temp_22 中。 对于浮点数，用 fadd 代替 add。 比较使用 icmp 与比较类型： %temp_2 = icmp slt i32 %temp_1, 10其中 slt 是“Signed Less Than”，即variable->name, node->variable->namespace_id, type_name(node->variable)); // 带初始化，则再生成一个赋值语句 if (node->initial != NULL) { ((Statement *) (node->initial))->generate_code((Statement *) (node->initial)); } } 赋值： static void generate_code(AssignStatement *node) { ((LValue *) (node->lhs))->generate_lvalue_code((LValue *) (node->lhs)); node->rhs->generate_rvalue_code(node->rhs); char *rvalue_ir = node->rhs->rvalue_ir(node->rhs); char *lvalue_ir = node->lhs->lvalue_ir(node->lhs); printf("store %s %s, %s* %s\n", type_string(((RValue *) (node->lhs))->type), rvalue_ir, type_string(((RValue *) (node->lhs))->type), lvalue_ir); free(rvalue_ir); free(lvalue_ir); }对expression来说，左值右值要分开，以普通变量为例： // 右值需从变量读取到寄存器才能使用 static void generate_rvalue_code(VariableReference *rValue) { char *rvalue_ir_string = ((RValue *) rValue)->rvalue_ir((RValue*) rValue); char *lvalue_ir_string = ((LValue*) rValue)->lvalue_ir((LValue *) rValue); printf("%s = load %s, %s* %s\n", rvalue_ir_string, type_name(rValue->variable), type_name(rValue->variable), lvalue_ir_string); free(rvalue_ir_string); free(lvalue_ir_string); } // 左值无需读取出来 static void generate_lvalue_code(VariableReference *lValue) { } // 做左值时ir中的变量名 static char *lvalue_ir(VariableReference *lValue) { char *result = malloc(128); sprintf(result, "%%%s_%zu", lValue->variable->name, lValue->variable->namespace_id); return result; } // 做右值时ir中的变量名 static char *rvalue_ir(VariableReference *rValue) { char *result = malloc(128); sprintf(result, "%%temp_%zu", rValue->temp_register_id); return result; }其他代码如何生成可以由读者自己想出来，对我的实现感兴趣的话请自行阅读代码。 参考资料 编译原理龙虎鲸三连： 《编译原理》——“龙书” 《现代编译原理：Ｃ语言描述》——“虎书” 《高级编译器设计与实现》——“鲸书” 参考词法 & 文法 C语言的词法 C语言的文法 LLVM IR llvm 官方网站，尤其是其语言参考 mapping high level constructs to llvm ir 1代码中将会使用C语言的面向对象编程，见用纯C实现面向对象编程。这东西用多了就有一种C语言远比C++好用的感觉（Linus一点都没说错）。 2其实在构造AST里我偷偷摸摸做了一丁点语义分析。 3其实是因为我懒。 |
【本文地址】
今日新闻 |
推荐新闻 |